home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / graph_alg / _strongcomp.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  3.1 KB  |  124 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _strongcomp.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. /*******************************************************************************
  18. *                                                                              *
  19. *  STRONG_COMPONENTS (strong connected components)                             *
  20. *                                                                              *
  21. *******************************************************************************/
  22.  
  23.  
  24. #include <LEDA/graph_alg.h>
  25.  
  26. static void scc_dfs(const graph& G, node v, node_array<int>& compnum,
  27.                                             node_data<int>& dfsnum,
  28.                                             node_list& unfinished,
  29.                                             list<node>& roots,
  30.                                             int& count1, int& count2 );
  31.  
  32.  
  33. int STRONG_COMPONENTS(const graph& G, node_array<int>& compnum)
  34. {
  35.   // int STRONG_COMPONENTS(graph& G, node_array<int>& compnum)
  36.   // computes strong connected components (scc) of digraph G
  37.   // returns m = number of scc 
  38.   // returns in node_array<int> compnum for each node an integer with
  39.   // compnum[v] = compnum[w] iff v and w belong to the same scc
  40.   // 0 <= compnum[v] <= m-1 for all nodes v
  41.  
  42.   list<node>     roots;
  43.   node_list      unfinished;
  44.   node_data<int> dfsnum(G,-1);
  45.  
  46.   int count1 = 0; 
  47.   int count2 = 0;
  48.  
  49.   node v;
  50.  
  51.   forall_nodes(v,G) 
  52.       if (dfsnum[v] == -1) 
  53.        scc_dfs(G,v,compnum,dfsnum,unfinished,roots,count1,count2);
  54.  
  55.   return count2;
  56. }
  57.  
  58.  
  59. static void scc_dfs(const graph& G, node v, node_array<int>& compnum,
  60.                                             node_data<int>& dfsnum,
  61.                                             node_list& unfinished,
  62.                                             list<node>& roots,
  63.                                             int& count1, int& count2 )
  64. {
  65.   node w;
  66.  
  67.   dfsnum[v] = ++count1;
  68.   unfinished.push(v);
  69.   roots.push(v);
  70.  
  71.   forall_adj_nodes(w,v)
  72.     { if (dfsnum[w]==-1) 
  73.        scc_dfs(G,w,compnum,dfsnum,unfinished,roots,count1,count2);
  74.       else 
  75.        if (unfinished(w))
  76.         while (dfsnum[roots.head()]>dfsnum[w])  roots.pop();
  77.      }
  78.  
  79.   if (v==roots.head()) 
  80.    { do { w=unfinished.pop();
  81.           /* w is an element of the scc with root v */
  82.           compnum[w] = count2;
  83.          } while (v!=w);
  84.      count2++;
  85.      roots.pop(); 
  86.     }
  87. }
  88.  
  89.  
  90.  
  91. int STRONG_COMPONENTS1(graph& G, node_array<int>& compnum)
  92. { 
  93.   node v,w;
  94.   int n = G.number_of_nodes();
  95.   int count = 0;
  96.  
  97.   node* V = new node[n+1];
  98.  
  99.   list<node> S;
  100.   node_array<int> dfs_num(G);
  101.   node_array<int> compl_num(G);
  102.   node_array<bool> reached(G,false);
  103.  
  104.   DFS_NUM(G,dfs_num,compl_num);
  105.  
  106.   forall_nodes(v,G) V[compl_num[v]] = v;
  107.  
  108.   G.rev();
  109.  
  110.   for(int i=n; i>0; i--)
  111.    { if ( !reached[V[i]] ) 
  112.       { S = DFS(G,V[i],reached);
  113.         forall(w,S) compnum[w] = count;
  114.         count++;
  115.        }
  116.     }
  117.  
  118.  delete V;
  119.  
  120.  return count;
  121.    
  122.  }
  123.  
  124.